def step(f, g, x, d, fk, gk, eps, ls):
    """
    Perform line search

    :param f: objective function
    :param g: gradient
    :param x: starting point
    :param d: direction
    :param fk: f(x0)
    :param gk: g(x0)
    :param eps: precision
    :param ls: line search
    :return: (#STOP, x_{k+1}, f_{k+1}, iterations)
    """
    if (gk @ d) > 0:
        d = -d
    a, ls_it = ls(f, g, x, d, fk, gk)
    x_new = x + a * d
    f_new = f(x_new)
    stop = abs(fk - f_new) < eps
    return stop, x_new, f_new, ls_it
